#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    string temp = "";
    bool flag = false;

    public:
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    void dfs(vector<vector<char>>& board, int x, int y, string word, int len, string temp){
        char ch = board[x][y];
        temp = temp + board[x][y];
        if(len == word.size()){
            if(temp == word){
                flag = true;
            }
            return; 
        }

        board[x][y] = '#';
        for(int i = 0; i != 4; i++){
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()){
                if(board[nx][ny] != '#'){
                    dfs(board, nx, ny, word, len+1, temp);
                }
            }
        }
        temp.pop_back();
        board[x][y] = ch;
    }
    //out of time
    bool ans1(vector<vector<char>>& board, string word){
        for(int i = 0; i != board.size(); i++){
            for(int j = 0; j != board[0].size(); j++){
                dfs(board, i, j, word, 1, temp);
            }
        }

        return flag;
    }



};

void test1(){
    Solution s;
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word = "ABCCED";
    bool ret = s.ans1(board, word);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word = "SEE";
    bool ret = s.ans1(board, word);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<vector<char>> board = {
        {'A','B','C','E'},
        {'S','F','C','S'},
        {'A','D','E','E'}
    };
    string word = "ABCB";
    bool ret = s.ans1(board, word);
    cout << ret << endl;
}

void test4(){
    Solution s;
    vector<vector<char>> board = {
        {'a','A','a','a','a','a'},
        {'a','a','A','A','a','A'},
        {'A','A','a','A','A','A'},
        {'a','A','a','a','a','A'},
        {'a','a','a','A','A','a'},
        {'a','a','A','A','a','a'}
    };
    string word = "AAaaAaaaaaAaAa";
    bool ret = s.ans1(board, word);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();
    test4();

    return 0;
}